package leetcode.solution;

/**
 * @author : zx
 * @version V1.0
 */
public class LongestAscString {

    /**
     * 对字符串数组按照最后一个字节进行快排
     * @param s
     * @return
     */
    public static String[] sort(String[] s, int low, int high){
        if (low < high){
            int start = low;
            int stop = high;
            String tmp = s[low];
            char[] ctmp = tmp.toCharArray();
            while (low < high){
                char[] clow = s[low].toCharArray();
                char[] chigh = s[high].toCharArray();
                while (chigh[chigh.length-1] > ctmp[ctmp.length-1] && low < high){
                    high--;
                    chigh = s[high].toCharArray();
                }
                s[low] = s[high];
                while (clow[clow.length-1] < ctmp[ctmp.length-1] && low < high){
                    low++;
                    clow = s[low].toCharArray();
                }
                s[high] = s[low];
            }
            s[low] = tmp;
            sort(s, start, low-1);
            sort(s, low+1, stop);
            return s;
        }else {
            return s;
        }
    }

    /**
     * 按照首尾字符和长度排序，"aaaa"应排在"abc"之前
     */
    public static boolean bigger(char[] a, char []b){

        if (a[0] > b[0]){
            // 首字母大返回true
            return true;
        }else if (a[0] < b[0]){
            return false;
        }else {
            // 首字母相等则比较末尾
            if (a[a.length-1] > b[b.length-1] ){
                return true;
            }else {
                return false;
            }
        }
    }

    /**
     * 对字符串数组按照第一个字节进行快排
     * @param s
     * @return
     */
    public static String[] sortFirst(String[] s, int low, int high){
        if (low < high){
            int start = low;
            int stop = high;
            String tmp = s[low];
            char[] ctmp = tmp.toCharArray();
            while (low < high){
                char[] clow = s[low].toCharArray();
                char[] chigh = s[high].toCharArray();
                while (bigger(chigh,ctmp) && low < high){
                    high--;
                    chigh = s[high].toCharArray();
                }
                s[low] = s[high];
                while (!bigger(clow,ctmp) && low < high){
                    low++;
                    clow = s[low].toCharArray();
                }
                s[high] = s[low];
            }
            s[low] = tmp;
            sort(s, start, low-1);
            sort(s, low+1, stop);
            return s;
        }else {
            return s;
        }
    }

    /**
     * 找到每一单词前最长的ascstring
     * @param s
     * @return
     */
    public static int longest(String[] s){
        // 最大长度
        int max = 0;
        // 先按首字母排序
        s = sortFirst(s, 0, s.length-1);
        // 用于记录排序后每个单词前最长的ascString长度
        int[] history = new int[s.length];
        for (int i = 0; i < s.length; i++){
            // i=0时需初始化history
            if (s[i].toCharArray().length > history[i]){
                history[i] = s[i].toCharArray().length;
                if (s[i].toCharArray().length > max){
                    max = s[i].toCharArray().length;
                }
            }
            for (int j = 0; j < i; j++){
                char[] sj = s[j].toCharArray();
                char[] si = s[i].toCharArray();
                // 首尾字符符合规则且根据history判断是否有必要更新
                if (sj[sj.length-1] <= si[0] && history[j]+si.length>history[i]){
                    // 更新max
                    if (history[j]+si.length > max){
                        max = history[j]+si.length;
                    }
                    history[i] = history[j]+si.length;
                }
            }
        }

        return max;
    }

    public static void main(String[] args){
        String[] s = new String[]{"dddd", "aadd", "ffxz", "cv"};
        for (String a : sortFirst(s, 0, s.length-1)){
            System.out.println(a);
        }
        System.out.println(longest(s));

    }
}
